1. Field of the Invention
The invention relates to motion estimation technology, more particularly to a motion estimator and a method implemented thereby for estimating motion vector of a video.
2. Description of the Related Art
In order to increase the efficiency of video compression in video encoders, it is general practice that not every pixel in every full image is encoded. Rather, pixel variations in different images are recorded using motion vectors, which are subsequently used for reconstruction back into the full images.
As the video sequence changes in motion, the pixels in the images change as well. In other words, the pixel on row (p), column (q) (also referred to as the pixel (p, q)) in a current image might originate from the pixel (g, h) in a previous image, for example. Generally speaking, a pixel set containing at least one pixel is used in the process of motion estimation. Therefore, in order to locate the most probable source of estimation (e.g., the pixel set that includes the pixel (g, h)), a conventional three-step search method including the following three steps is used. It should be noted herein that in the following description, it is assumed that the pixel (a, b) in the previous image is defined as an initial center of search.
In the following description, for a particular pixel set size, a pixel set (a, b) refers to the set of pixels within an area of the pixel set size where the pixel (a, b) serves as a reference pixel.
In step 1, with reference to FIG. 1, for each of pixel sets (a±4, b), (a, b±4) and (a±4, b±4) in the previous image, a matching error with respect to the pixel set (p, q) in the current image is calculated. A pixel set (c, d) in the previous image resulting in the least matching error is located, and is taken as an updated center of search. In the example shown in FIG. 1, the pixel set (c, d) resulting in the least matching error is the pixel set (a−4, b). In particular, the matching error is calculated according to the pixels in each of the pixel sets (a±4, b), (a, b±4) and (a±4, b±4) in the previous image and the pixel set (p, q) in the current image.
In step 2, for each of pixel sets (c±2, d), (c, d±2) and (c±2, d±2) in the previous image, a matching error with respect to the pixel set (p, q) in the current image is calculated. A pixel set (e, f) in the previous image resulting in the least matching error is located, and is taken as an updated center of search. In the example shown in FIG. 1, the pixel set (e, f) resulting in the least matching error is the pixel set (c, b−2).
In step 3, for each of pixel sets (e±1, f), (e, f±1) and (e±1, f±1) in the previous image, a matching error with respect to the pixel set (p, q) in the current image is calculated. A pixel set (g, h) in the previous image resulting in the least matching error is located, and is taken as the most probable source pixel set. The vector between the pixel set (g, h) and the pixel set (p, q) is the motion vector. In the example shown in FIG. 1, the pixel set (g, h) resulting in the least matching error is the pixel set (e+1, f+1).
However, although the conventional three-step search method is capable of locating the most probable source of estimation, a significant amount of computations is required for calculating the matching errors. In addition, the amount of computations increases as image resolution and range of search increase, thereby resulting in a high manufacturing cost for motion estimators.